package 柱状图中最大的矩形;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: AirMan
 * @date: 2025/5/28 13:27
 * @description:
 */
public class Solution2 {
    public int largestRectangleArea(int[] heights) {
        // 单调栈
        // 分别寻找两侧第一次出现一个数字比自己小（且记录的是索引值，不是高度），所以单调栈需要是单调递减的
        // 进一步思考当出现 栈顶所代表的元素就是当前柱子，当前遍历的元素如果符合条件,那么他就是右侧第一个矮柱子
        // 栈中第二个元素就是左边第一个矮柱子

        // 如果数组是单调递增，那么将不会触发while为Trye的条件
        // 如果数组是单调递减，那么同样也不会触发while为Trye的条件
        // 解决思路就是破环单调性！在数组的前后末尾分别添加数字0


        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }
        heights = newHeights;

        int size = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        int result = 0;

        // 计算面积
        for (int i = 0; i < size; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                // 计算面积
                Integer index = stack.pop();
                int width;
                if (stack.isEmpty()) {
                    // 表明一个柱子左侧没有矮柱子，-1方便了width的计算
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }
                int height = heights[index];
                result = Math.max(result, width * height);
            }
            stack.push(i);
        }

        return result;
    }
}
